package 二叉树系列;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class StandardIterateTraversal {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if(root==null)  return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode treeNode = stack.peek();
            if(treeNode!=null){
                stack.pop();
                if(treeNode.right!=null)    stack.push(treeNode.right);
                if(treeNode.left!=null)     stack.push(treeNode.left);
                stack.push(treeNode);
                stack.push(null);
            }else{
                stack.pop();    //弹出Null
                treeNode = stack.pop(); //弹出此时的栈顶元素，也即是要取得值
                result.add(treeNode.val);
            }
        }
        return result;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if(root==null)  return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode treeNode = stack.peek();
            if(treeNode!=null){
                stack.pop();

                if(treeNode.right!=null)    stack.push(treeNode.right);
                stack.push(treeNode);
                stack.push(null);
                if(treeNode.left!=null)     stack.push(treeNode.left);

            }else{
                stack.pop();    //弹出Null
                treeNode = stack.pop(); //弹出此时的栈顶元素，也即是要取得值
                result.add(treeNode.val);
            }
        }
        return result;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if(root==null)  return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode treeNode = stack.peek();
            if(treeNode!=null){
                stack.pop();
                stack.push(treeNode);
                stack.push(null);
                if(treeNode.right!=null)    stack.push(treeNode.right);
                if(treeNode.left!=null)     stack.push(treeNode.left);

            }else{
                stack.pop();    //弹出Null
                treeNode = stack.pop(); //弹出此时的栈顶元素，也即是要取得值
                result.add(treeNode.val);
            }
        }
        return result;
    }
}
